package com.LeeCode;

import java.util.Arrays;

/**
 * 构建字典序最大的可行序列
 */

public class Code1718 {
    public static void main(String[] args) {
        int n = 5;
        System.out.println(Arrays.toString(new Code1718().constructDistancedSequence(n)));
    }

    public int[] constructDistancedSequence(int n) {
        int len = 2 * n - 1;
        int[] ans = new int[len];
        backtrace(0, n, new boolean[n + 1], ans);
        return ans;
    }

    private boolean backtrace(int index, int n, boolean[] used, int[] ans) {
        // 找到下一个空位置
        while (index < ans.length && ans[index] != 0) {
            index++;
        }

        // 终止条件：所有位置都填满了
        if (index == ans.length) {
            return true;
        }

        // 要字典序最大，从大往小填
        for (int i = n; i >= 1; i--) {
            if (used[i]) continue; // 该数字已经使用过了
            // 计算第二个数字的间距
            int secondPos = i == 1 ? index : index + i;
            // 检查边界和位置是否为空
            if (secondPos < ans.length && ans[index] == 0 && ans[secondPos] == 0) {
                ans[index] = i;
                ans[secondPos] = i;
                used[i] = true;
                if (backtrace(index + 1, n, used, ans)) return true;
                used[i] = false;
                ans[index] = 0;
                ans[secondPos] = 0;
            }
        }
        return false;
    }
}
